package demo17;

import java.util.ArrayList;
import java.util.List;

/**
 * 综合练习_括号生成
 * https://leetcode.cn/problems/IDBivT/
 */
class Solution {

    List<String> ret = new ArrayList<>();
    StringBuffer path = new StringBuffer();
    int[] count = new int[2]; // 0下标( 1下标)
    int n;
    public List<String> generateParenthesis(int n) {
        this.n = n;
       dfs('(');
        return ret;
    }

    private void dfs(char chars) {
        count[chars - '(']++;
        // 减枝
        if(count[1] > count[0] || count[0] > n) {
            // 右括号比左括号多, 出现错误
            count[chars - '(']--;
            return;
        }
        path.append(chars);
        // 满足条件
        if(count[0] == count[1] && count[0] == n) {
            // 满足条件, 放入到返回数组中
            ret.add(path.toString());
            count[chars - '(']--;
            path.deleteCharAt(path.length()-1);
            return;
        }
        // 递归
        dfs('(');
        dfs(')');
        path.deleteCharAt(path.length()-1);
        count[chars - '(']--;
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> list = solution.generateParenthesis(3);
        for(String str : list) {
            System.out.println(str);
        }
    }
}